


import random

class Palace:

    def __init__(self, size):
        """
        @size: integer, 3 is as usual.
        self.size is initialized as size.
        self.len is initialized as size**2.
        self.pri(mary) is initialized 'None' array of self.len * self.len.
        self.res(ult) is initialized 'None' array of self.len * self.len.
        """
        self.size = size
        self.len = size**2
        pri = self.len * [None]
        pri = [self.len * [None] for all in pri]
        self.pri = pri
        res = self.len * [None]
        res = [self.len * [None] for all in res]
        self.res = res
        self.__result__ = []
        self.__index__ = -1
        
        
        pass

    def define(self, val, x, y, p = None):
        """
        @val: integer
        @x: integer, coordinate x
        @y: integer, coordinate y
        @p: array, value array of Palace
        (value, x, y) is used to define one blank in self.pri(mary) according to
        (x, y) coordinate and value.
        Or p is used to copy a value array to self.pri(mary).        
        """
        if not p:
            if self.checkRule(val, x, y):
                self.pri[x][y] = val
                self.__push__((val, x, y))
            else:
                self.pri[x][y] = None
        else:
            for i in range(self.len):
                self.pri[i] = p[i][:]
                for j in range(self.len):
                    self.__push__((p[i][j], i, j))
        pass

    def multiDefine(self, valTuple):
        """
        @valTuple: tuple, value tuple
        Every element of valTuple is a tuple (value, x, y)
        'define' is invoked for every tuple.
        """
        for all in valTuple:
            val = all[0]
            x = all[1]
            y = all[2]
            self.define(val, x, y)
            self.__push__((val, x, y))
            


    def step(self):
        """
        To calculate one 'None' to integer value if possible
        according to the known Palace.
        Return 'ret' is the list of calculated value coordinate.
        The Palace is updated according to the calculated value.
        Algorithm:
        1. get tempPri value array from self.pri(mary), and
        get tempList value array from self.res(ult)
        2. for certain a position (i, j), if it is None, 1 to 9 (if size is 3)
        are tried. After Rule checked, the values from 1 to 9 which is passed
        are grouped to a list. The list is defined in tempDict(ionary),
        whose key is the coordinate (i, j).
        The array tempList collects the value from tempDict. Every element of
        tempList is a list of valid values.
        3. deal with tempList:
        Consider: if one valid value can only occur in certain a blank, (means
        it can not occur in other blanks of same row, or same column,
        or same palace.), then it is the answer of this blank.
        If there is no such a valid value, it is going on checking whether
        some blank has only one valid value, then it is the answer of this
        blank.
        """
        ret = []
        tempDict = {}
        tempPri = self.pri[:]
##        print "I'm in step"
##        self.printP(tempPri)
        tempList = self.res[:]
        for i in range(self.len):
            for j in range(self.len):
                if tempPri[i][j] == None:
                    for val in range(1, self.len+1):
                        if self.checkRule(val, i, j):
##                            print val
                            tempDict[(i, j)] = tempDict.get((i, j), [])
                            tempDict[(i, j)].append(val)
                tempList[i][j] = tempDict.get((i, j), [])
        self.tempDict = tempDict
        self.tempList = tempList


                    
        for i in range(self.len):
            for j in range(self.len):
                if tempList[i][j]:
                    tRow, tCol, tPal = self.getTuple(i, j, tempList)

##                    retval = self.outstand(tempList[i][j], tRow)
##                    if retval != None:
##                        self.define(val, i, j)
##                        ret.append((i, j))
##                        return ret
##
##                    retval = self.outstand(tempList[i][j], tCol)
##                    if retval != None:
##                        self.define(val, i, j)
##                        ret.append((i, j))
##                        return ret
##
##                    retval = self.outstand(tempList[i][j], tPal)
##                    if retval != None:
##                        self.define(val, i, j)
##                        ret.append((i, j))
##                        return ret
                        
                    for val in tempList[i][j]:
                        tFlag = True
                        for r in tRow:
                            if id(tempList[i][j]) == id(r):
                                continue
                            if val in r:
                                tFlag = False
                                break
                        if tFlag:
                            self.define(val, i, j)
                            ret.append((i, j))
                            return ret
                            
                    for val in tempList[i][j]:
                        tFlag = True
                        for c in tCol:
                            if id(tempList[i][j]) == id(c):
                                continue
                            if val in c:
                                tFlag = False
                                break
                        if tFlag:
                            self.define(val, i, j)
                            ret.append((i, j))
                            return ret
                            
                    for val in tempList[i][j]:
                        tFlag = True 
##                        ti = (i%self.size)*self.size + (j%self.size + 1)
                        for p in tPal:
                            if id(tempList[i][j]) == id(p):
                                continue
                            if val in p:
                                tFlag = False
                                break
                        if tFlag:
                            self.define(val, i, j)
                            ret.append((i, j))
                            return ret
                            
                    
        count = 0
        for all in tempDict.keys():
            if len(tempDict[all]) == 1:
                self.define(tempDict[all][0], all[0], all[1])
                ret.append((all[0], all[1]))
                return ret
            else:
                count += 1
                continue

        
        self.printP(self.res)
        print tempDict
        self.tempDict = tempDict

        return ret


##    def outstand(self, baselist, objlist):
##        for val in baselist:
##            tFlag = True
##
##            for all in objlist:
##                if baselist == all:
##                    continue
##                if val in all:
##                    tFlag = False
##                    break
##            if tFlag:
##                return val
##
##        return None

    def printP(self, p):
        """
        @p: array, the value array of Palace
        Print
        i i i i i i i i i
        i i i i i i i i i
        i i i i i i i i i
        i i i i i i i i i
        i i i i i i i i i
        i i i i i i i i i
        i i i i i i i i i
        i i i i i i i i i
        i i i i i i i i i
        where 'i' is integer from 1 to 9 if the size of Palace is 3
        """
        for i in range(self.len):
            row = ''
            for j in range (self.len):
                row = row + str(True and p[i][j] or 'x') + self.size*' '
            print row + self.size/2*'\n'
        print '================================================================='    
        pass

    def getTuple(self, x, y, p):
        """
        @x: integer, coordinate x
        @y: integer, coordinate y
        @p: array, the value array of Palace
        Return '(row, col, pal)', the tuple of three value lists
        The length of list is size**2
        """
        row = p[x]
        col = [p[i][y] for i in range(self.len)]
        pal = []
        tempX = x/self.size
        tempY = y/self.size
        for i in range(tempX*self.size, (tempX+1)*self.size):
            for j in range(tempY*self.size, (tempY+1)*self.size):
                pal.append(p[i][j])

        return (row, col, pal)
        

    def checkRule(self, val, x, y):
        """
        @val: integer
        @x: integer, coordinate x
        @y: integer, coordinate y
        Return 'True' if value is not in its Row, Colume, and Palace
        Return 'False' if value has been in its Row, Colume, or Palace
        """
        gT = self.getTuple(x, y, self.pri)
##        print gT
##        print "I'm in checkRule"
##        self.printP(self.pri)
        checkRow = self.checkList(val, gT[0])
        checkCol = self.checkList(val, gT[1])        
        checkPal = self.checkList(val, gT[2])

        if (checkRow and checkCol and checkPal):
            return True
        else:
            return False
        
        pass


    def checkList(self, val, slist):
        """
        @val: integer
        @slist: list
        Return 'True' if value is not in slist
        Return 'False' if value is in slist
        """
        if val not in slist:
            return True
        else:
            return False

    def judgeRun(self):
        """
        Return 'True' if all blank is filled and rule check is passed.
        Return 'False' if it can't be continued.
        Return '(value, x, y)' if some rule check is not passed.
        """        
        while True:

            ret = self.step()
            retState = self.judgeStep(ret) 
            p.printP(p.pri)
                
            if retState == True:
##                p.printP(p.pri)
                return True

            elif retState == False:
##                p.printP(p.pri)
                return False

            elif type(retState) is tuple:
##                p.printP(p.pri)
                return retState

            
    def judgeStep(self, retList):
        """
        @retList: list, a return coordinate list from self.step
        Return 'True' if all blank is filled and rule check is passed.
        Return 'False' if it can't be continued.
        Return '(value, x, y)' if some rule check is not passed.        
        """
        winFlag = True
        correctFlag = True
        for i in range(9):
            winFlag = winFlag and self.checkList(None, self.pri[i])
            if not winFlag:
                break
            for j in range(9):
                correctFlag = correctFlag and (not self.checkRule(self.pri[i][j], i, j))
                if not correctFlag:
                    return (self.pri[i][j], i, j)
                else:
                    pass

        if winFlag == True:
            return True   
               
        if retList == []:
            return False


    def resolve(self, palace, index, result):
        retBool = judgeRun()
        if retBool == True:
            return True
        elif retBool == False:
            p = tryInsert(palace)
            resolve(p, )
            

        for items in coodinates:
            pass
            
        
        pass

    def __push__(self, valueTuple):
        self.__result__.append(valueTuple)
        self.__index__ += 1

    def __pop__(self):
        retTuple = self.__result__.pop(self.__index)
        self.__index__ -= 1
        return retTuple

    def tryInsert():
        pass
        




if __name__ == '__main__':

    p = Palace(3)    
    
    p.define(4, 1, 2)
    p.define(2, 1, 5)
    p.define(7, 1, 7)
    p.define(1, 2, 4)
    p.define(3, 2, 5)
    p.define(2, 2, 6)
    p.define(8, 2, 7)
    p.define(8, 3, 0)
    p.define(9, 3, 3)
    p.define(6, 3, 5)
    p.define(4, 3, 7)
    p.define(7, 4, 0)
    p.define(1, 4, 2)
    p.define(2, 4, 7)
    p.define(9, 4, 8)
    p.define(1, 6, 0)
    p.define(8, 6, 1)
    p.define(5, 6, 6)
    p.define(3, 6, 7)
    p.define(7, 6, 8)
    p.define(5, 7, 3)
    p.define(6, 7, 4)
    p.define(4, 7, 8)
    p.define(7, 8, 2)
    p.define(9, 8, 6)
##    p.define(6, 8, 7)


    retVal = p.judgeRun()
    if retVal == True:
        p.printP(p.pri)
        print "Congradulations, You Win!"

    elif retVal == False:
        p.printP(p.pri)
        print "No answer found so far."

    elif type(retVal) is tuple:
        p.printP(p.pri)
        print "Error for " + str(retVal)

    else:
        print "It is impossible..."
        print retVal

    
